Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6. The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.
Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.
In [1]:
from sympy import sieve, primepi
N = 10 ** 7
n = int(N ** 0.5)
min_ratio = 1.005
best_n = None
primes = list(sieve.primerange(1, N))
pi = primepi(n)
num_primes = len(primes)
for i in range(pi, -1, -1):
p = primes[i]
ratio = p / (p - 1)
if ratio > min_ratio:
break
for j in range(i+1, num_primes):
q = primes[j]
n = p * q
if n > N:
break
if p / (p - 1) > min_ratio:
break
if sorted(str(n)) == sorted(str(n - p - q + 1)):
ratio = 1.0 * p * q / (p - 1) / (q - 1)
if ratio < min_ratio:
min_ratio = ratio
best_n = n
print(best_n)
Discussion: The ratio n/φ(n) is equal to the product of p/(p-1) for all distinct prime factors p of n. We may assume that n has no repeated factors.
If n is prime then φ(n) = n - 1, so the digits of φ(n) cannot be a permutation of the digits of n.
If n is the product of three or more prime factors, then its smallest prime factor is less than 200, so n/φ(n) > 1.005.
Suppose that n is the product of two distinct prime factors p and q (p < q). Then n/φ(n) = p/(p-1) * q/(q-1). If the minimum value realized in this case is less than 1.005, then we have found the optimal value of n.